Doubly Linked List

-return to blog- • -return to wiki-

Data Structure

A linked list that is like a singly linked list but with forward and backward pointers on each node. The node has (key | next pointer | previous pointer).

(ALGS201x)

Pros

  • Takes advantage of random empty spaces in memory, regardless of location.
  • Constant time to insert at or remove from the front
  • Constant time to insert at or remove from the back, if doubly-linked or with tail
  • Constant time to insert between nodes or remove a node
  • PopBack() is O(1) vs. O(n) in singly linked lists
  • AddBefore(Node,Key) is O(1) vs. O(n) in singly linked lists

Cons

  • No random access
  • No good for repeatedly accessing a particular element often

(ALGS201x, DEV285x)

Operations - List API

  • PushFront(Key) - add to front - O(1)
  • Key TopFront() - return front item - O(1)
  • PopFront() - remove front item - O(1)
  • PushBack(Key) - add to back - AKA Append(Key) - (no tail pointer - O(n)) - (tail pointer - O(1))
  • Key TopBack() - return back item - (no tail pointer - O(n)) - (tail pointer - O(1))
  • PopBack() - remove back item - O(1)
  • Boolean Find(Key) - is key in list? - O(n)
  • Erase(Key) - remove key from list - O(n)
  • Boolean Empty() - is list empty? - O(1)
  • AddBefore(Node, Key) - add key before node - O(1)
  • AddAfter(Node, Key) - add key after node - O(1)

(ALGS201x)

PushFront(key)


* [nod](/view/Nod)[e](/view/E) <-- new [nod](/view/Nod)[e](/view/E)
* [nod](/view/Nod)[e](/view/E).key <-- key
* [nod](/view/Nod)[e](/view/E).next <-- [head](/view/Head)
* [head](/view/Head) <-- [nod](/view/Nod)[e](/view/E)
* if tail = nil:
* * tail <-- [head](/view/Head)

PopFront()


* if [head](/view/Head) = nil:
* * [E](/view/E)RROR: [e](/view/E)mpty list
* [head](/view/Head) <-- [head](/view/Head).next
* if [head](/view/Head) = nil:
* * tail <-- nil

PushBack(key)


* [nod](/view/Nod)[e](/view/E) <-- new [nod](/view/Nod)[e](/view/E)
* [nod](/view/Nod)[e](/view/E).key <-- key; [nod](/view/Nod)[e](/view/E).next = nil
* if tail = nil:
* * [head](/view/Head) <-- tail <-- [nod](/view/Nod)[e](/view/E)
* * [nod](/view/Nod)[e](/view/E).prev <-- nil
* [e](/view/E)lse: 
* * tail.next <-- [nod](/view/Nod)[e](/view/E)
* * [nod](/view/Nod)[e](/view/E).prev <-- tail
* * tail <-- [nod](/view/Nod)[e](/view/E)

PopBack()


* if [head](/view/Head) = nil: [E](/view/E)RROR: [e](/view/E)mpty list
* if [head](/view/Head) = tail:
* * [head](/view/Head) <-- tail <--nil
* [e](/view/E)lse: 
* * tail <-- tail.prev
* * tail.next <-- nil

AddAfter(node, key)


* [nod](/view/Nod)[e](/view/E)2 <-- new [nod](/view/Nod)[e](/view/E)
* [nod](/view/Nod)[e](/view/E)2.key <--key
* [nod](/view/Nod)[e](/view/E)2.next <-- [nod](/view/Nod)[e](/view/E).next
* [nod](/view/Nod)[e](/view/E)2.prev <-- [nod](/view/Nod)[e](/view/E) 
* [nod](/view/Nod)[e](/view/E).next <-- [nod](/view/Nod)[e](/view/E)2
* if [nod](/view/Nod)[e](/view/E)2.next =/= nil:
* * [nod](/view/Nod)[e](/view/E)2.net.prev <-- [nod](/view/Nod)[e](/view/E)2
* if tail = [nod](/view/Nod)[e](/view/E): 
* * tail <-- [nod](/view/Nod)[e](/view/E)2

AddBefore(node, key)


* [nod](/view/Nod)[e](/view/E)2 <-- new [nod](/view/Nod)[e](/view/E)
* [nod](/view/Nod)[e](/view/E)2.key <--key
* [nod](/view/Nod)[e](/view/E)2.next <-- [nod](/view/Nod)[e](/view/E)
* [nod](/view/Nod)[e](/view/E)2.prev <--[nod](/view/Nod)[e](/view/E).prev
* [nod](/view/Nod)[e](/view/E).prev <-- [nod](/view/Nod)[e](/view/E)2
* if [nod](/view/Nod)[e](/view/E)2.prev =/= nil:
* * [nod](/view/Nod)[e](/view/E)2.prev.next <-- [nod](/view/Nod)[e](/view/E)2
* if [head](/view/Head) = [nod](/view/Nod)[e](/view/E): 
* * [head](/view/Head) <-- [nod](/view/Nod)[e](/view/E)2

(ALGS201x)